#include <stdio.h>
#include <stdlib.h>

int canPartition(int* nums, int numsSize);
int recursionCheck(int remainNum, int* nums, int numsSize);
void quickSort(int* nums, int left, int right);

int main(){
	int nums[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,97,95};
	int numsSize = sizeof(nums)/sizeof(int);
	int t = canPartition(nums, numsSize);
	printf("%s\n", t ? "true" : "false");
	return 0;
}

int canPartition(int* nums, int numsSize) {
    int sum = 0, max = 0;
    int i;
    quickSort(nums, 0, numsSize-1);
    for(i = 0; i < numsSize; ++i){
        sum += nums[i];
        max = max < nums[i] ? nums[i] : max;
    }
	if(sum%2 != 0 || sum/2 < max)
		return 0;
	int desValue = sum/2;
	if(recursionCheck(desValue, nums, numsSize))
        return 1;
    return 0;
}

int recursionCheck(int remainNum, int* nums, int numsSize){
    if(remainNum == 0)
        return 1;
    else if(remainNum < 0)
        return 0;
    int trueFlag = 0;
    int i;
    for(i = 0; i < numsSize; ++i){
        trueFlag |= recursionCheck(remainNum-nums[i], nums+(i+1), numsSize-(i+1));
        if(trueFlag)
            break;
    }
    return trueFlag;
}

void quickSort(int* nums, int left, int right){
	if(left >= right)
		return;
	int i = left;
	int j = right;
	int pivot = nums[left];
	while(i < j){
		while(i < j && pivot > nums[j])
			j--;
		nums[i] = nums[j];
		while(i < j && pivot <= nums[i])
			i++;
		nums[j] = nums[i];
	}
	nums[i] = pivot;
	quickSort(nums, left, i-1);
	quickSort(nums, i+1, right);
}